package com.cjm.algorithm.queue;

import java.util.HashMap;
import java.util.Map;

public class YuShui42 {

    /**
     * 对于每根柱子而言， 我们只需要找出【其左边最高的柱子】和【其右边最高的柱子】
     * 对左右的最高柱子取一个最小值, 再和当前柱子的高度做一个比较， 即可得出当前位置可以接下的雨水。
     * 同时，边缘的柱子不可能接到雨水（某一侧没有柱子）
     *
     *
     * 这道题， 后来我也是想这么做的， 但是不知道下手， 不知道怎么去写这个代码
     * 1、走到一个位置
     * 2、遍历其左侧的最高列
     * 3、如果左侧最高的， 比当前位置还低， 那么说明这个是一个凸列
     * 4、遍历其右侧的最高列
     * 5、如果右侧最高列小于当前列， 那么这也是一个凸列
     * 6、到这里我终于知道， 我为什么会想不通了， 因为我是想一下子算完一个凹算完， 但是呢， 并不是这样的，
     * 而应该是一列一列的算
     * 7、要在心中想象有那么一堵墙， 每一列每列的计算
     *
     * @param height
     * @return
     */
    private static int gongshuisanyepushu(int[] height) {
        int n = height.length;
        int ans = 0;
        // 因为边上的柱子， 没个卵用
        for (int i = 1; i < n - 1; i++) {
            // 当前的柱子是多高呢？
            int cur = height[i];
            // 获取当前位置的左边最大值
            int l = Integer.MIN_VALUE;
            for (int j = i - 1; j >= 0; j--) {
                // 一直递归完， 找到左边最大值
                l = Math.max(l, height[j]);
            }
            if (l <= cur) continue;

            // 获取当前位置的右边边最大值
            int r = Integer.MIN_VALUE;
            for (int j = i + 1; j < n; j++) {
                r = Math.max(r, height[j]);
            }
            if (r <= cur) continue;

            ans += Math.min(l, r) - cur;
        }
        return ans;
    }

    /**
     * 对于每根柱子而言， 我们只需要找出【其左边最高的柱子】和【其右边最高的柱子】
     *
     * @param height
     * @return
     */
    public int trap(int[] height) {
        return dongtaiguihua(height);
    }

    /**
     * 动态规划
     *
     * @param height 这个数组
     * @return 容量
     */
    private static int dongtaiguihua(int[] height) {
        if (height.length <= 2) {
            return 0;
        }

        // 每个节点左侧的最高列
        int[] left = new int[height.length];
        // 每个节点右侧的最高列
        int[] right = new int[height.length];

        // 第1个元素的最高的就是它自己
        left[0] = height[0];
        // 最后一个元素， 右侧最高的就是它自己
        right[height.length - 1] = height[height.length - 1];

        // 这里是从最左侧开始计算
        for (int i = 1; i < height.length; i++) {
            left[i] = Math.max(height[i], left[i - 1]);
        }

        // 这里是从最右侧开始计算
        for (int i = height.length - 2; i >= 0; i--) {
            right[i] = Math.max(height[i], right[i + 1]);
        }

        int sum = 0;
        for (int i = 1; i < height.length; i++) {
            // 你看， 这里， 还是一个一个计算的, 也就是一列一列计算的
            int count = Math.min(left[i], right[i]) - height[i];
            if (count > 0) {
                sum += count;
            }
        }

        return sum;
    }

    private static int shuanzhizhen(int[] height) {
        // 一共有多少根柱子
        int length = height.length;
        // 能接到多少雨水
        int ans = 0;
        for (int i = 1; i < length - 1; i++) {
            int cur = height[i];
            // 找出左侧最高的
            int left = Integer.MIN_VALUE;
            for (int j = i - 1; j >= 0; j--) {
                left = Math.max(left, height[j]);
            }
            if (left <= cur) {
                continue;
            }

            int right = Integer.MIN_VALUE;
            for (int j = i + 1; j < length; j++) {
                right = Math.max(right, height[j]);
            }
            if (right <= cur) {
                continue;
            }
            ans += Math.min(left, right) - cur;
        }
        return ans;
    }
}
